Computer systems are highly useful for compiling and assimilating large amounts of data. Computer systems frequently include graphic displays capable of displaying curves. FIG. 1 illustrates a curve 2 that may be displayed on a typical graphics display system.
Graphics display systems generally include a memory for storing a digital representation of the curve to be displayed. In a primitive system this might include an extremely large memory that stores a digital value which represents the curve to be displayed. A high-resolution display system using this method would require an extremely large memory. Such a primitive system would be too slow when initially generating the digital values which represent the curve, and would also be slow when manipulating the curve, such as when the curve is rotated or relocated on the display. Because of these problems, most computer display systems utilize the Bezier spline method of modeling curves.
A Bezier spline, often referred to as a Bezier curve, is a mathematical construct for curves and curved surfaces. The most frequently used Bezier curve for two-dimensional graphic systems is the cubic Bezier curve. A cubic Bezier curve requires four control points which define the curve. Once the four points are specified, the curve is defined. However, as is well known to those skilled in the art, higher order Bezier curves may be used to create highly complex curves in two, three or higher dimensions.
To use cubic Bezier curves to construct an arbitrary curve such as curve 2 of FIG. 1, the curve may be partitioned into a number of individual arcs. This is illustrated in FIG. 1 wherein the curve 2 is divided into three arcs. Between points 4 and 6 curve 2 is divided into an arc 8, between points 6 and 10 curve 2 is divided into an arc 12, and between points 10 and 14 curve 2 is divided into an arc 16. To construct the arc 8 using a cubic Bezier curve, the arc end points 4 and 6 plus two additional points, control points 18 and 20, are selected. By properly selecting the control points 18 and 20 and the end points 4 and 6, the arc 8 can be generated using a well known reiterative process. This process is repeated for arcs 12 and 16 using their selected control points. Thus, the curve 2 can be defined by ten Bezier control points. In a similar manner, almost any desired curve can be generated from a set of selected control points using the Bezier curve technique.
While Bezier curves permit a curve to be described by a small set of data points, when the Bezier curve itself is to be displayed on a display screen the data values for the sequence of points on the display screen, called pixels, that trace out the curve must be specified. Since determining each and every data point on an arc of a curve is a slow, computationally inefficient process, it has been found highly beneficial to approximate the Bezier curve. An advantage of doing this is that the Bezier curve can be approximated very closely by a finite set of straight line segments. The number of line segments required depends upon several factors including the rate of curvature of the desired curve and the resolution of the display screen. Approximating an arc by a finite set of straight lines segments is particularly advantageous because determining the set of points comprising a line segment can be done very efficiently. The reduction of a Bezier curve into a set of straight line segments that approximates the curve, or at least an arc of the curve, is called "rendering" the curve.
Note that the above discussion is equally applicable to printers as well as display screens. The pixel size on a typical laser printer is different from the pixel size on a typical video display screen. However, the same problems encountered in rendering a Bezier curve on a display screen are present when rendering a curve on a laser printer or any other type of graphics printer, such as a vector plotter which does not use pixels.
A typical prior art method of rendering the Bezier curve is known as recursive subdivision. The process is illustrated in FIG. 2 wherein an arc 22 is to be closely approximated by a set of line segments. Two control points referred to as end points 24 and 26 of the arc 22 together with control points 28 and 30 define the arc 22 via a cubic Bezier curve. These four control points are determined in a well known manner. The initial step in rendering the curve is to determine whether the line segment 38 extending between points 24 and 26 is a "close enough" approximation to the arc 22 that the line segment 38 can be displayed as an approximation of the arc 22. If the line segment is within the resolution of the display screen (i.e., within a pixel of where the actual arc should be located on the screen), then further computations will yield no qualitative improvement in the display. The actual resolution depends on the display device. For example, on a typical video display terminal, there are 72 pixels per inch, while a laser printer has 300 or even 600 pixels per inch. Thus, the degree of accuracy of calculations depends on the display device.
The method of determining the amount of error in a recursive subdivision process is to form a line segment 38 extending between points 24 and 26. Then the magnitude of a line segment 40, perpendicular to line segment 38 and extending through control point 28, and the magnitude of a line segment 42, also perpendicular to line segment 38 but extending through point 30, are determined. The magnitudes of the line segments 40 and 42 are then checked as to whether they are both smaller than a predetermined test magnitude, such as the dimension of one pixel. If line segments 40 and 42 are both smaller than the test magnitude, the line segment 38 is deemed to be a close enough approximation of the arc 22 that it can be displayed as the arc.
However, if the magnitude of either of the line segments 40 or 42 is greater than the test magnitude, the line segment 38 is not a sufficiently accurate representation of the arc 22 and is an unsuitable approximation of the arc for display purposes. In that event, the arc 22 is subdivided into two parts, each defined by four control points. The four control points for each part are determined as follows. First, the midpoint of each of line segments 32, 34, and 36 is determined, specifically points 44, 46, and 48, respectively. Next the midpoints of line segments extending between points 44 and 46 and between points 46 and 48 are determined, specifically points 50 and 52, respectively. Finally, the midpoint of a line segment 54 extending between points 50 and 52 is determined, that point being point 56. The arc 22 passes through point 56. At point 56, the arc 22 is tangent to the line segment 54 connecting points 50 and 52. The two portions of the arc 22 can now be defined.
The first portion 22a of arc 22 is defined using points 24, 44, 50, and 56 as Bezier control points and the second portion 22b of arc 22 is defined by using points 56, 52, 48, and 26 as Bezier control points. After the two portions 22a and 22b of arc 22 are found, the line segments 60 and 62 drawn between the end points 24 and 56 and drawn between end points 56 and 26, respectively are then tested using the procedure described above to determine whether the line segments 60 and 62 are a sufficiently accurate approximation of their respective arc portions 22a and 22b that they can be used to display that portion of the arc 22. If one or more of the arc portions are not defined closely enough by line segments drawn between the respective control points, the Bezier curve for that arc portion is subdivided using the above procedure. The procedure is reiterated until each portion of the arc 22 is deemed to be closely enough approximated for display purposes by a resulting set of line segments.
By continuing the above process it is possible to approximate the arc 22 to any desired degree of accuracy. It is very important to stop the rendering of the Bezier curve when a given set of line segments approximate the arc with sufficient accuracy that a more accurate set of line segments is not required. This is because of the very large number of mathematical operations required to render a highly accurate curve, because most computer graphics systems, whether display screens or printers, are typically low resolution devices, because the amount of memory required to store the resulting set of line segments grows quickly as the accuracy of the approximation increases, and because of the finite speed of computer graphic systems.
The above prior art technique of determining when a set of line segments closely approximates a Bezier curve is computationally inefficient. The prior art technique requires the determination of the lengths of the line segments 40 and 42. It requires, in each reiteration, a calculation of the shortest distance between two Bezier control points and a line segment, such as control points 28 and 30 and the line segment 38. To do this, the location of points 57 and 58 must be determined so that the magnitudes of the line segments 40 and 42 can be calculated. Calculating the location of points 57 and 58 is computationally inefficient; this inefficiency becomes highly pronounced when performed the large number of times required by some computer graphic displays when rendering the curve.
Another prior art method of rendering a Bezier curve is to mathematically analyze the formula used to define the Bezier curve to determine if a straight line segment drawn between the Bezier end points is a sufficiently close approximation for the purposes of the user that it may be used to approximate the Bezier curve.
A Bezier curve can be represented mathematically by the generalized formula: EQU f(t)=.SIGMA.b.sub.k B.sub.k.sup.n (t)
where ##EQU1## The formula is valid for a Bezier curve of any order where the order of the Bezier is n. Thus, the equation for a cubic Bezier curve (n=3) is: EQU f(t)=b.sub.0 (1-t).sup.3 +b.sub.1 3(1-t).sup.2 t+b.sub.2 3(1-t)t.sup.2 +b.sub.3 t.sup.3
in which b.sub.0 through b.sub.3 are the four Bezier control points required to define the curve. The above equation is valid for any number of dimensions. The formula is applied independently to each dimension by using vectors to define the function in each dimension. For the sake of simplicity, only a single equation is discussed. As t varies from zero to one, the function f(t) defined by the Bezier control points is traced out as shown by the curve 100 in FIG. 3A.
The parametric approach to rendering the Bezier curve initially attempts to render the curve 100 with a single straight line segment 106 drawn between the Bezier end points 102 and 104, as shown in FIG. 3A. This step may be thought of as taking a single step from Bezier end point 102, the initial position of the function f(t) at t=0, to Bezier end point 104. If the error term indicates that the line segment 106 is not accurate enough to be used as an approximation of the Bezier curve 100, prior art systems apply a mathematical operator to the function f(t) which cuts the "step size" in half so that the function now defines only the first curve portion 108 of the Bezier curve 100 as shown in FIG. 3B. The function defines the curve portion 108 between the current position at Bezier end point 102 and a new end point 116, which is the point on the curve 100 for the function f(t) where t=1/2. Note that the point 116 is the same point 56, at which line 54 is tangent to the arc 22 in FIG. 2.
A mathematical operator well known in the art is applied to the function f(t) to decrease the step size. This operator is often called an "Adjust Down Operator." Prior to applying the Adjust Down Operator, the function f(t) defines the entire curve 100 from the initial position at Bezier end point 102 to Bezier end point 104. After applying the Adjust Down Operator to the function f(t), the function now defines a first half portion 108 of the curve 100 from the initial position at Bezier end point 102 to the point 116 on the curve 100 for the function f(t) where t=1/2. Systems of the prior art will analyze the function f(t) for the one-half step size to determine if the line segment 112 drawn between end point 102 and midpoint 116 is an accurate approximation of the curve portion 108. If the line segment 112 is not sufficiently accurate to approximate the curve portion 108, the system decreases the step size again by applying the Adjust Down Operator to the function f(t) a second time. The function f(t) now defines the first quarter portion 118 of the curve 100 from the initial position at Bezier end point 102 to the midpoint 122 of the curve portion 108 as shown in FIG. 3C (the second quarter portion being indicated by the reference numeral 124). The step size continues to be decreased by one-half until the line segment is sufficiently accurate to be an adequate approximation of a portion of the curve.
At that point in time, systems of the prior art apply a different operator, commonly called a "Step Forward Operator," to the function f(t). The Step Forward Operator effectively moves the current position of the function by an amount equal to the current step size. For example, if a line segment 120 in FIG. 3C drawn between end point 102 and point 122 were determined to be sufficiently accurate to approximate the curve portion 118, the system will use the line segment 120 to approximate the curve portion 118 and apply the Step Forward Operator to the function f(t) to move the function to the point 122 on the curve. Prior to applying the Step Forward Operator, the function f(t) defines the curve portion 118 from the initial position at Bezier end point 102 to the end point 122. After applying the Step Forward Operator, the current position of the function f(t) is moved to the end point 122; the function now defines the curve portion 124 from the current position at point 122 to the end point 116. Note that the step size of the function has not been altered by applying the Step Forward Operator. Prior art systems will apply the same process to the function f(t) for the curve portion 124, applying the Adjust Down Operator if necessary, or applying the Step Forward Operator if the line segment 126 is close enough to the curve portion 124 that the line segment 126 can be used to approximate the curve portion 124.
If the line segment 126 is sufficiently accurate to approximate the curve portion 124, the system will apply a third operator, commonly called an "Adjust Up Operator" to the function f(t) which doubles the step size of subsequent applications of the Forward Step Operator. The step size is doubled by the Adjust Up Operator. Prior to applying the Adjust Up Operator, the function f(t) defines the curve portion 124 from the current position at end point 122 to end point 116. After applying the Adjust Up Operator, the function defines a double sized curve portion 124 and 128 from the current position at end point 122 to a new end point 132 as shown in FIG. 3D. Thus, the system will determine if a line segment 130 drawn between point 122 and point 132 is a sufficiently accurate approximation of the curve portions 124 and 128. If the line segment 130 is sufficiently accurate to approximate the curve portions 124 and 128, the system uses the line segment 130 and applies the Step Forward Operator to the function f(t) to move the current location of f(t) to point 132 at the end of line segment 130. This process of halving or doubling the step size as the function moves along the Bezier curve is known in the art as adaptive forward differencing (AFD).
Ideally, AFD will render the curve 100 with a minimum number of line segments. As will be discussed in greater detail below, this does not occur because of the difficulty in evaluating the error terms of the function f(t).
As is well known in the art, the formula for AFD is merely a manipulation of the generalized Bezier formula. The manipulation, called a change in the basis, results in the following formula for the AFD basis: EQU f(t)=a.sub.0 A.sub.0 (t)+a.sub.1 A.sub.1 (t) . . . +a.sub.k A.sub.k (t)
where A.sub.k (t)=((t-k+1)/k)*A.sub.k-1 (t), A.sub.0 (t)=1. For the cubic Bezier curve, the most commonly used curve, the factors A.sub.0 through A.sub.3 are given by the following equations: EQU A.sub.0 (t)=1 EQU A.sub.1 (t)=t EQU A.sub.2 (t)=1/2(t)(t-1) EQU A.sub.3 (t)=1/6(t)(t-1)(t-2)
where the function is expressed in terms of the AFD factors. To evaluate the function at time, t=t+1, it is possible to use the following equations: EQU A.sub.0 (t+1)=1=A.sub.0 (t) EQU A.sub.1 (t+1)=A.sub.0 (t)+A.sub.1 (t) EQU A.sub.2 (t+1)=A.sub.1 (t)+A.sub.2 (t) EQU A.sub.3 (t+1)=A.sub.2 (t)=A.sub.3 (t)
to express the function f(t+1) in terms of the function f(t). One can apply the Forward Step Operator to evaluate the function f(t+1) in terms of the function f(t). The following equation expresses the function f(t+1) in the AFD basis: EQU f(t+1)=(a.sub.0 +a.sub.1)A.sub.0 (t)+(a.sub.1 +a.sub.2)A.sub.1 (t)+(a.sub.2 +a.sub.3)A.sub.2 (t)+(a.sub.3)A.sub.3 (t)
resulting in the equation: EQU f(t+1)=(a.sub.0 ')A.sub.0 (t)A.sub.0 (t)+(a.sub.1 ')A.sub.1 (t)+(a.sub.2 ')A.sub.2 (t)+(a.sub.3 ')A.sub.3 (t)
where a.sub.0 +a.sub.1 =a.sub.0 ', a.sub.1 +a.sub.2 =a.sub.1 ', a.sub.2 +a.sub.3 =a.sub.2 ', and a.sub.3 =a.sub.3 '. Note that f(t+1) can be evaluated by using the vector terms a.sub.0 ' through a.sub.3 '.
The use of simple operators applied to the function f(t) will increase the computational efficiency of rendering a Bezier curve. Thus, the mathematical approach of AFD to rendering a Bezier curve is an improvement over the graphical techniques previously described. However, the system is still faced with the problem of determining how many subdivisions are necessary to render a satisfactory approximation of the Bezier curve. Using the techniques of AFD, an error term can be calculated. But, the error term of the AFD equation is difficult to evaluate. As a result, prior art systems resort to an alternative method of determining the accuracy of the rendered curve. The most common approach in AFD is to subdivide repeatedly until each line segment is no greater than a selected test magnitude which is often selected as being one pixel in length. Thus, the curve is repeatedly subdivided and the length of the line segment, calculated by the equation a.sub.0 '-a.sub.0, is no greater than a pixel long.
There are several disadvantages to using AFD to subdivide until line segments are no greater than one pixel long. The most obvious disadvantage is that many more subdivisions may be performed than are actually required to render an accurate approximation of a Bezier curve, since often a line segment several pixels long provides a suitable approximation, particularly for very flat curves and straight lines.
Another disadvantage of AFD is that the points generated by the AFD technique are not always the same as the points generated by the recursive subdivision method of the prior art described above. Note that recursive subdivision would never have resulted in line segment 130 being used to approximate curve portions 124 and 128 in FIG. 3D. Since recursive subdivision always subdivides the curve in half, the point 116 will be the end point of a line segment used to approximate the curve 100. Thus, recursive subdivision will always result in point 116 being a Bezier control point while the AFD techniques may result in a line segment that does not use point 116 as a control point for the function f(t).
Because the control points may be different, the AFD technique is not guaranteed to be bidirectional, that is the Bezier control points generated starting at one end of the Bezier curve are not necessarily the same control points that are generated starting from the other end of the curve. Erasure of a graphic image using AFD requires that the system start at the same end of the curve for erasing as for creating a curve. This is a disadvantage when erasing a curve from a computer display screen since it may often be more efficient to erase from the other end of the Bezier curve.
The recursive subdivision method has the advantage that it is not directionally dependent. The same Bezier control points are generated when starting at either end of the Bezier curve. The recursive subdivision method has the disadvantage that it is computationally inefficient in rendering a curve as discussed above.
Therefore, it would be useful to have a computationally efficient system and method of rendering Bezier curves and determining the accuracy with which the resulting straight line segments approximate the curve.